Mobile communicators within cellular communication systems are often required to search for and track one or more base stations within the system during normal operation. Often, a communicator will need to search for and track a number of different base stations simultaneously. As can be appreciated, these base station search functions can consume a significant amount of the computational and time resources of a mobile communicator. These functions may also consume energy resources within the mobile communicator (e.g., by depleting batteries within a handheld communicator). Therefore, there is a general need for base station search techniques and structures that are time, computation, and/or energy efficient.